#include <stdlib.h>
#include <malloc.h>

#include "linkedlist.h"


/* Node related functions */
ptr_node_t llist_make_node(void *d,ptr_node_t n,ptr_node_t p)
{
  ptr_node_t node;

  node=(ptr_node_t)malloc(sizeof(struct node_t));

  node->data=d;
  node->next=n;
  node->prev=p;

  return node;
}

/* Iterator related functions */
ptr_iterator_t llist_iter_make_iterator(ptr_node_t h)
{
  ptr_iterator_t iter;

  iter=(ptr_iterator_t)malloc(sizeof(struct iterator_t));

  iter->header=h;
  iter->current=h;

  return iter;
}

int llist_iter_has_next(ptr_iterator_t iter)
{
  return iter->current->next!=iter->header;
}

void *llist_iter_next(ptr_iterator_t iter)
{
  iter->current=iter->current->next;
  return iter->current->data;
}


/* List related functions */
ptr_list_t llist_make_list()
{
  ptr_list_t list;

  list=(ptr_list_t)malloc(sizeof(struct list_t));
  
  list->header=llist_make_node(NULL,NULL,NULL);
  list->header->next=list->header;
  list->header->prev=list->header;
  list->size=0;

  return list;
}

ptr_list_t llist_clone_list(ptr_list_t q)
{
  ptr_list_t list;
  ptr_iterator_t p;

  /*
  list=(ptr_list_t)malloc(sizeof(struct list_t));

  list->header=make_node();
  list->header->next=list->header;
  list->header->prev=header;
  list->size=0;    
  */
  list=llist_make_list();

  p=llist_get_nodes(q);
  while (llist_iter_has_next(p))
    llist_add_last(list,llist_iter_next(p));

  free(p);
  
  return list;
}

void llist_set_comparator(ptr_list_t list,int (*f)(void *,void *))
{
  list->compare=f;
}

void llist_set_converter(ptr_list_t list,int (*f)(void *))
{
  list->to_string=f;
}

void *llist_add_first(ptr_list_t list,void *d)
{
  ptr_node_t p;

  p=llist_make_node(d,list->header->next,list->header);

  list->header->next->prev=p;
  list->header->next=p;
  list->size++;
	
  return d;
}

void *llist_add_last(ptr_list_t list,void *d)
{
  ptr_node_t p;

  p=llist_make_node(d,list->header,list->header->prev);

  list->header->prev->next=p;
  list->header->prev=p;
  list->size++;

  return d;
}

void *llist_get_first(ptr_list_t list)
{
  ptr_node_t p;
  void *data;

  p=list->header->next;

  list->header->next=p->next;
  p->next->prev=list->header;
  list->size--;

  data=p->data;

  free(p);

  return data;
}

void *llist_get_last(ptr_list_t list)
{
  ptr_node_t p;
  void *data;

  p=list->header->prev;

  p->prev->next=list->header;
  list->header->prev=p->prev;
  list->size--;

  data=p->data;

  free(p);

  return data;
}

void *llist_peek_first(ptr_list_t list)
{
  return list->header->next->data;
}

void *llist_peek_last(ptr_list_t list)
{
  return list->header->prev->data;
}

int llist_get_size(ptr_list_t list)
{
  return list->size;
}

int llist_is_empty(ptr_list_t list)
{
  return list->size==0;
}

void llist_remove(ptr_list_t list,void *d)
{
  ptr_node_t p;

  for (p=list->header->next;p!=list->header;p=p->next)
    if (list->compare(d,p->data)==0)
      {
	p->prev->next=p->next;
	p->next->prev=p->prev;
	list->size--;

	// remove p->data if it is not pointed to by d
	if (p->data!=d)
	  free(p->data);

	break;
      }	

  free(p);
}

void llist_remove_reference(ptr_list_t list,void *d)
{
  ptr_node_t p;

  for (p=list->header->next;p!=list->header;p=p->next)
    if (p->data==d)
      {
	p->prev->next=p->next;
	p->next->prev=p->prev;
	list->size--;
	// do not remove p->data because it is still pointed to by d
	break;
      }	

  free(p);
}

ptr_iterator_t llist_get_nodes(ptr_list_t list)
{
  return llist_iter_make_iterator(list->header);
}

int llist_contains(ptr_list_t list,void *o)
{
  return llist_search(list,o)!=NULL;
}

void *llist_search(ptr_list_t list,void *o)
{
  ptr_node_t p;

  for (p=list->header->next;p!=list->header;p=p->next)
    if (list->compare(o,p->data)==0)
      return p->data;
	
  return NULL;
}

void *llist_to_array(ptr_list_t list,size_t size)
{
  /*
  ptr_node_t p;
  int i=0;
  char *o;

  if (list->size==0)
    return NULL;

  o=(char *)malloc(list->size*size);
	
  for (p=list->header->next;p!=list->header;p=p->next)
    o[size*i++]=(char *)(p->data);

  return (void *)o;
  */

  return NULL;
}

ptr_list_t llist_get_permutations(ptr_list_t list)
{
  //	return (new Permutator(this)).permutate();
  return NULL;
}

char *llist_to_string(ptr_list_t list)
{
  /*
	String s="[";
	
	for (Node p=header.next;p!=header;p=p.next)
	    s+=p.data+",";

	if (s.endsWith(","))
	    s=s.substring(0,s.length()-1);

	s+="]";

	return s;

   */
  return NULL;
}

int llist_get_rank(ptr_list_t list,void *o)
{
  ptr_node_t p;
  int rank=0;

  for (p=list->header->next;p!=list->header;p=p->next)
    if (list->compare(p,p->data)==0)
      return rank;
    else
      rank++;
	
  return -1;
}

